home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / procssng / ccs / ccs-11tl.lha / lbl / hips / libsrc / h_fill_holes.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-17  |  7.3 KB  |  336 lines
  1.  
  2. /*  h_fill_holes.c                          Brian Tierney,  LBL  3/90
  3.  *
  4.  *   converted to HIPS2            Felix Huang,    LBL  8/91
  5.  *
  6.  *  fills holes in a binary images
  7.  *
  8.  *  usage: fill_holes [-s NN] < infile > outfile
  9.  *    where -s NN the size of holes to look for ( default = 2)
  10.  */
  11.  
  12. /*   This program is copyright (C) 1990, Regents  of  the
  13. University  of  California.   Anyone may reproduce this software,
  14. in whole or in part, provided that:
  15. (1)  Any copy  or  redistribution  must  show  the
  16.      Regents  of  the  University of California, through its
  17.      Lawrence Berkeley Laboratory, as the source,  and  must
  18.      include this notice;
  19. (2)  Any use of this software must reference this  distribu-
  20.      tion,  state that the software copyright is held by the
  21.      Regents of the University of California, and  that  the
  22.      software is used by their permission.
  23.  
  24.      It is acknowledged that the U.S. Government has  rights
  25. to this software under  Contract DE-AC03-765F00098 between the U.S.
  26. Department of Energy and the University of California.
  27.  
  28.      This software is provided as a professional  academic  contribu-
  29. tion  for  joint exchange.  Thus it is experimental, is pro-
  30. vided ``as is'', with no warranties of any kind  whatsoever,
  31. no  support,  promise  of updates, or printed documentation.
  32. Bug reports or fixes may be sent to the author, who may or may
  33. not act on them as he desires.
  34. */
  35.  
  36. /*   Author:  Brian L. Tierney
  37.  *            Lawrence Berkeley Laboratory
  38.  *            Imaging and Distributed Computing Group
  39.  *            email: bltierney@lbl.gov
  40. */
  41.  
  42. #define Calloc(x,y) (y *)calloc((unsigned)(x), sizeof(y))
  43.  
  44. #include <stdio.h>
  45. #include <hipl_format.h>
  46.  
  47. extern int hole_size;
  48. extern Boolean ends_only;
  49.  
  50. #define PVAL 255
  51.  
  52. void      look_for_holes(), fill_holes(), line_fill();
  53.  
  54. extern int nrow;
  55. extern int ncol;
  56. extern int i_ocol;
  57.  
  58. byte    **roi1, **roi2;
  59.  
  60. h_fill_holes(hdi, hdo)
  61.     struct header *hdi, *hdo;
  62. {
  63.     i_to_r(hdi->firstpix);
  64.     look_for_holes();
  65.     r_to_o(hdo->firstpix);
  66. }
  67.  
  68.  
  69. /********************************************************************/
  70. i_to_r(imagei)            /* input image to roi1     */
  71.     byte     *imagei;
  72. {
  73.     int       x, y;
  74.  
  75.     roi1 = Calloc(nrow, byte *);
  76.     for (y = 0; y < nrow; y++)
  77.     roi1[y] = Calloc(ncol, byte);
  78.  
  79.     roi2 = Calloc(nrow, byte *);
  80.     for (y = 0; y < nrow; y++)
  81.     roi2[y] = Calloc(ncol, byte);
  82.  
  83.     for (y = 0; y < nrow; y++, imagei = imagei + i_ocol)
  84.     for (x = 0; x < ncol; x++)
  85.         roi1[y][x] = imagei[x];
  86. }
  87.  
  88. r_to_o(imageo)            /* roi2 to output image     */
  89.     byte     *imageo;
  90. {
  91.     int       x, y;
  92.  
  93.     for (y = 0; y < nrow; y++, imageo = imageo + i_ocol)
  94.     for (x = 0; x < ncol; x++)
  95.         imageo[x] = roi2[y][x];
  96. }
  97.  
  98.  
  99. /********************************************************************/
  100. void
  101. look_for_holes()
  102. {
  103.     register int i, j;
  104.  
  105.     for (i = hole_size; i < nrow - hole_size; i++)
  106.     for (j = hole_size; j < ncol - hole_size; j++)
  107.         if (roi1[i][j] > 0) {    /* pixel is part of an object */
  108.         roi2[i][j] = roi1[i][j];
  109.         fill_holes(i, j);
  110.         }
  111. }
  112.  
  113. /*************************************************************/
  114. void
  115. fill_holes(i, j)
  116.     int       i, j;
  117. {
  118.     /*
  119.      * NOTE: since we are scanning all pixels, we only need to look for holes
  120.      * in 2 directions, the other 2 directions will be checked later when at
  121.      * another pixel location
  122.      */
  123.  
  124.     register int i1, j1, i2, j2, jj, ii;
  125.  
  126.     int       dist;
  127.  
  128.     dist = 2;            /* start 2 pixels away from point */
  129.  
  130.     while (dist <= hole_size + 1) {
  131.     i1 = i - dist;
  132.     j1 = j - dist;
  133.     i2 = i + dist;
  134.     j2 = j + dist;
  135.     if (i1 < 0)
  136.         i1 = 0;
  137.     if (j1 < 0)
  138.         j1 = 0;
  139.     if (i2 > nrow - 1)
  140.         i2 = nrow - 1;
  141.     if (j2 > ncol - 1)
  142.         j2 = ncol - 1;
  143.  
  144.     for (jj = j1; jj < j2; jj++) {
  145.         if (roi1[i2][jj] > 0)
  146.         draw_line(j, i, jj, i2);
  147.     }
  148.  
  149.     for (ii = i1; ii < i2; ii++) {
  150.         if (roi1[ii][j2] > 0)
  151.         draw_line(j, i, j2, ii);
  152.     }
  153.     dist++;
  154.     }
  155. }
  156.  
  157. /*********************************************************************/
  158. draw_line(x1, y1, x2, y2)
  159.     int       x1, y1, x2, y2;
  160. {
  161.     int       a, b;
  162.  
  163.     if (ends_only == TRUE) {
  164.     a = side_cnt(y1, x1);    /* check if 1st point is a end of a line */
  165.     b = corner_cnt(y1, x1);
  166. #ifdef TEST
  167.     if (a > 1 || b > 1)    /* not an end */
  168. #endif
  169.         if (a > 1 || b > 1 || (a == 1 && b == 1))    /* not an end */
  170.         return;
  171.  
  172.     a = side_cnt(y2, x2);    /* check if 2nd point is a end of a line */
  173.     b = corner_cnt(y2, x2);
  174. #ifdef TEST
  175.     if (a > 1 || b > 1)    /* not an end */
  176. #endif
  177.         if (a > 1 || b > 1 || (a == 1 && b == 1))    /* not an end */
  178.         return;
  179.     }
  180.     line_fill(roi2, x1, y1, x2, y2);
  181. }
  182.  
  183. /*********************************************************************/
  184.  
  185. int
  186. side_cnt(i, j)
  187.     int       i, j;        /* current array location */
  188. {
  189.     int       cnt = 0;
  190.  
  191.     if (i > 0)
  192.     if (roi1[i - 1][j] > 0)
  193.         cnt++;
  194.     if (j > 0)
  195.     if (roi1[i][j - 1] > 0)
  196.         cnt++;
  197.     if (i < nrow - 1)
  198.     if (roi1[i + 1][j] > 0)
  199.         cnt++;
  200.     if (j < ncol - 1)
  201.     if (roi1[i][j + 1] > 0)
  202.         cnt++;
  203.     return (cnt);
  204. }
  205.  
  206. /*********************************************************************/
  207. int
  208. corner_cnt(i, j)
  209.     int       i, j;        /* current array location */
  210. {
  211.     int       cnt = 0;
  212.  
  213.     if (i > 0 && j > 0)
  214.     if (roi1[i - 1][j - 1] > 0)
  215.         cnt++;
  216.     if (i < nrow - 1 && j < ncol - 1)
  217.     if (roi1[i + 1][j + 1] > 0)
  218.         cnt++;
  219.     if (i < nrow - 1 && j > 0)
  220.     if (roi1[i + 1][j - 1] > 0)
  221.         cnt++;
  222.     if (i > 0 && j < ncol - 1)
  223.     if (roi1[i - 1][j + 1] > 0)
  224.         cnt++;
  225.  
  226.     return (cnt);
  227. }
  228.  
  229. /***************************************************************/
  230. int
  231. count_neighbors(c, r)
  232.     register int c, r;        /* max value returned is 8 */
  233. {
  234.     int       neighbors = 0, tx, ty;
  235.  
  236.     tx = ncol - 1;
  237.     ty = nrow - 1;
  238.  
  239.     if (r > 0)
  240.     if (roi1[r - 1][c] > 0)
  241.         neighbors++;
  242.     if (r < ty)
  243.     if (roi1[r + 1][c] > 0)
  244.         neighbors++;
  245.  
  246.     if (c > 0)
  247.     if (roi1[r][c - 1] > 0)
  248.         neighbors++;
  249.     if (c < tx)
  250.     if (roi1[r][c + 1] > 0)
  251.         neighbors++;
  252.  
  253.     if (r < ty && c < tx)
  254.     if (roi1[r + 1][c + 1] > 0)
  255.         neighbors++;
  256.  
  257.     if (r > 0 && c > 0)
  258.     if (roi1[r - 1][c - 1] > 0)
  259.         neighbors++;
  260.  
  261.     if (r > 0 && c < tx)
  262.     if (roi1[r - 1][c + 1] > 0)
  263.         neighbors++;
  264.  
  265.     if (r < ty && c > 0)
  266.     if (roi1[r + 1][c - 1] > 0)
  267.         neighbors++;
  268.  
  269.     return (neighbors);
  270. }
  271.  
  272. /********************************************************************/
  273. void
  274. line_fill(buf, x1, y1, x2, y2)    /* Bresenhams's scan conversion algorithm */
  275.     byte    **buf;
  276.     int       x1, y1, x2, y2;
  277.  /*
  278.   * this code adapted from:   Digital Line Drawing by Paul Heckbert from
  279.   * "Graphics Gems", Academic Press, 1990
  280.   */
  281. {
  282.     int       d, x, y, ax, ay, sx, sy, dx, dy;
  283.  
  284.     /* absolute value of a */
  285. #ifndef ABS
  286. #define ABS(a)          (((a)<0) ? -(a) : (a))
  287. #endif
  288.  
  289.     /* take binary sign of a, either -1, or 1 if >= 0 */
  290. #define SGN(a)          (((a)<0) ? -1 : 1)
  291.  
  292.     if (x1 == x2 && y1 == y2) {
  293.     /* single point, don 't need to scan convert */
  294.     buf[y1][x1] = PVAL;
  295.     return;
  296.     }
  297.     dx = x2 - x1;
  298.     ax = ABS(dx) << 1;
  299.     sx = SGN(dx);
  300.  
  301.     dy = y2 - y1;
  302.     ay = ABS(dy) << 1;
  303.     sy = SGN(dy);
  304.  
  305.     x = x1;
  306.     y = y1;
  307.     if (ax > ay) {        /* x dominant */
  308.     d = ay - (ax >> 1);
  309.     for (;;) {
  310.         buf[y][x] = PVAL;
  311.         if (x == x2)
  312.         return;
  313.         if (d >= 0) {
  314.         y += sy;
  315.         d -= ax;
  316.         }
  317.         x += sx;
  318.         d += ay;
  319.     }
  320.     } else {            /* y dominant */
  321.  
  322.     d = ax - (ay >> 1);
  323.     for (;;) {
  324.         buf[y][x] = PVAL;
  325.         if (y == y2)
  326.         return;
  327.         if (d >= 0) {
  328.         x += sx;
  329.         d -= ay;
  330.         }
  331.         y += sy;
  332.         d += ax;
  333.     }
  334.     }
  335. }
  336.